/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.util.iterators;

import java.util.Arrays;
import java.util.NoSuchElementException;

import mosdi.util.IupacStringConstraints;

/** Iterator that enumerates (in lexicographical order) all IUPAC patterns
 *  conforming to given constraints. */
public class IupacPatternIterator extends LexicographicalIterator {
	int length;
	/** Contains a list of characters that are to be placed
	 *  in the remaining part of the string. */
	int[][] remainingCharacters;
	/** Frequencies of the remaining character as given in 
	 *  remainingCharacters. */
	IupacStringConstraints[] remainingConstraints;
	/** Current position in array remainingCharacters,
	 *  i.e. current[i]=remainingCharacters[i][currentPositions[i]] */
	int[] currentPositions;
	/** Current string. */
	int[] current;
	int currentLeftmostChangedPos;
	int lastLeftmostChangedPos;
	
	public IupacPatternIterator(int length) {
		int[] minFrequencies = {0,0,0,0};
		int[] maxFrequencies = {length,length,length,length};
		init(length, new IupacStringConstraints(minFrequencies, maxFrequencies));
	}
	
	public IupacPatternIterator(int length, IupacStringConstraints constraints) {
		init(length, constraints);
	}
	
	private void init(int length, IupacStringConstraints constraints) {
		this.length = length;
		current = new int[length];
		currentPositions = new int[length];
		for (int i=0; i<length; ++i) currentPositions[i]=-1;
		remainingConstraints = new IupacStringConstraints[length];
		remainingConstraints[0] = constraints;
		remainingCharacters = new int[length][];
		remainingCharacters[0] = constraints.validFirstCharacters(length);
		for (int i=0; i<length; ++i) {
			if (!step(i)) {
				current=null;
				return;
			}
		}
		currentLeftmostChangedPos=0;
		lastLeftmostChangedPos=-1;
	}
	
	/** Increases character at position. Returns false if there are
	 *  no characters left for this position (end of enumeration).
	 */
	private boolean step(int position) {
		int j = ++currentPositions[position];
		if (j<remainingCharacters[position].length) {
			int c = remainingCharacters[position][j];
			current[position] = c;
			// compute remaining characters of next position
			if (position+1<length) {
				IupacStringConstraints newConstraints = remainingConstraints[position].minus(c); 
				remainingConstraints[position+1] = newConstraints; 
				remainingCharacters[position+1] = newConstraints.validFirstCharacters(length-position-1);
				currentPositions[position+1]=-1;
			}
			return true;
		} else {
			currentPositions[position]=-1;
			return false;
		}
	}
	
	public boolean hasNext() {
		return current!=null;
	}

	public int[] next() {
		if (current==null) throw new NoSuchElementException();
		int[] result = Arrays.copyOf(current, length);
		lastLeftmostChangedPos=currentLeftmostChangedPos;
		int pos = length-1;
		for (;pos>=0;--pos) {
			if (step(pos)) break;
		}
		currentLeftmostChangedPos=pos;
		if (pos<0) {
			current=null;
		} else {
			++pos;
			for (;pos<length;++pos) {
				step(pos);
			}
		}
		return result;
	}

	public int[] peek() {
		return Arrays.copyOf(current, current.length);
	}
	
	/** Advance to next character at given position, that means a subsequent call
	 *  to next() will return the next string in lexicographical order, such that
	 *  leftmostChangedPosition<=position. */
	public void skip(int position) {
		if (current==null) return;
		if (currentLeftmostChangedPos<=position) return;
		for (;position>=0;--position) {
			if (step(position)) break;
		}
		currentLeftmostChangedPos=position;
		if (position<0) {
			current=null;
		} else {
			++position;
			for (;position<length;++position) {
				step(position);
			}
		}
	}
	
	/** Skips the given number of strings. */
	public void skipByNumber(long number) {
		if (current==null) return;
		if (number==0) return;
		if (number<0) throw new IllegalArgumentException();
		long multiplicity = 1;
		int pos = length-1;
		while (multiplicity<=number) {
			for (;pos>=0;--pos) {
				if (step(pos)) break;
			}
			number -= multiplicity;
			if (pos<0) {
				current = null;
				return;
			}
			multiplicity = (pos==length-1)?1:remainingConstraints[pos+1].validStringCount(length-pos-1);
		}
		currentLeftmostChangedPos = pos;
		++pos;
		for (;pos<length;++pos) {
			step(pos);
			while (true) {
				multiplicity = (pos==length-1)?1:remainingConstraints[pos+1].validStringCount(length-pos-1);
				if (multiplicity<=number) {
					boolean stepDone = step(pos);
					assert stepDone;
					number -= multiplicity; 
				} else {
					break;
				}
			}
		}
	}
	
	/** Returns the leftmost position that changed when the last returned
	 *  string was generated. */
	public int getLeftmostChangedPosition() {
		return lastLeftmostChangedPos;
	}
	
	@Override
	public int getStringLength() {
		return length;
	}

	public void remove() {
		throw new UnsupportedOperationException();
	}
}
